#include<iostream>
#include<vector>
#include<time.h>
using namespace std;
//递归版本
void _mergesort(vector<int>&arr,vector<int>&tem,int left,int right)
{
    if(left>=right) return;
    int mid=(right-left)/2+left;
    _mergesort(arr,tem,left,mid);
    _mergesort(arr,tem,mid+1,right);
    //进行归并
    int begin1=left;int end1=mid;
    int begin2=mid+1;int end2=right;
    int index=left;
    while(begin1<=end1&&begin2<=end2)
    {
        arr[begin1]<=arr[begin2]?tem[index++]=arr[begin1++]:tem[index++]=arr[begin2++];
    }
    while(begin1<=end1) tem[index++]=arr[begin1++];
    while(begin2<=end2) tem[index++]=arr[begin2++];
    for(int i=left;i<=end2;i++)
    {
        arr[i]=tem[i];
    }
}
void mergesort1(vector<int>&arr)
{
    if(arr.size()<=1) return;
      vector<int> tmp(arr.size());
      _mergesort(arr,tmp,0,arr.size()-1);
}
void mergesort2(vector<int>&arr)
{
    int n=arr.size();
    if(n<=1) return;
    vector<int>tem(n);
    for(int i=1;i<=n-1;i*=2)//控制步长 1 2 4 8
    {
        for(int j=0;j<=n-1;j+=2*i)//控制begin1
        {
            int begin1=j;
            int end1=begin1+i-1;
            int begin2 =end1+1;
            if(begin2>=n) break;//说明右边不存在
            int end2=min(begin2+i-1,n-1);
            int index=j;
            while(begin1<=end1&&begin2<=end2)
            {
                arr[begin1]<=arr[begin2]?tem[index++]=arr[begin1++]:tem[index++]=arr[begin2++];
            }
            while(begin1<=end1) tem[index++]=arr[begin1++];
            while(begin2<=end2)tem[index++]=arr[begin2++];
            for(int k=j;k<=end2;k++) arr[k]=tem[k];
        }
    }
}
int main()
{
	int n; cin >> n;
	vector<int>arr1(n);
	vector<int>arr2(n);
	vector<int>arr3(n);

	srand((unsigned int)time(NULL));
	for (int i = 0; i < n; i++)
	{
		arr1[i] = rand() + i;
		arr2[i] = arr1[i];
		arr3[i] = arr1[i];
	}
	for (auto& ch : arr1) cout << ch << " ";
	cout << endl;
	mergesort2(arr1);
	for (auto& ch : arr1) cout << ch << " ";
}